class code2 {
    //最大子数组和：分治
    public int maxSubArray(int[] nums) {
        //如果全是负数
        int m = nums[0];
        for(int x:nums) m = Math.max(m,x);
        if(m <= 0) return m;
        return dfs(nums,0,nums.length-1)[3];
    }

    public int[] dfs(int[] nums,int l,int r) {
        //递归出口
        if(l==r) {
            int t = Math.max(nums[l],0);
            return new int[]{nums[l],t,t,t};
        }
        //划分两个子区间，分别求解
        int mid = (l+r)>>1;
        int[] left = dfs(nums,l,mid);
        int[] right = dfs(nums,mid+1,r);

        //组合左右子区间的信息，得到当前区间的信息
        int[] ans = new int[4];
        ans[0] = left[0] + right[0];//当前区间和
        ans[1] = Math.max(left[1],left[0]+right[1]);//当前区间前缀max
        ans[2] = Math.max(right[2],right[0]+left[2]);//当前区间后缀max
        ans[3] = Math.max(Math.max(left[3],right[3]),left[2]+right[1]);//最大子数组和
        return ans;

    }
}
